class Solution {
public:
    int tribonacci(int n) {
        if(n<2){return n;}
        else
        {
            if(n==2){return 1;}
            else{
                int*Dp=new int[n+1];
                Dp[0]=0;
                Dp[1]=1;
                Dp[2]=1;
                for(int i=3;i<n+1;i++)
                {
                    Dp[i]=Dp[i-3]+Dp[i-2]+Dp[i-1];
                }
                return Dp[n];
            }
        }
    }
};